package datastructure.tree.twochatree;

/**
 * 二叉树深度优先遍历(前中后序遍历)-递归版本
 *
 * @author 杨 强
 * @package datastructure.tree.two
 * @createTime 2023-03-20 21:55
 */
public class TreeDeepErgodic01 {
    public static void main(String[] args) {
        // 构建一个二叉树
        /*
                1
               / \
              2   3
             /   / \
            4   5   6
         */
        TreeNode node = new TreeNode(
                new TreeNode(new TreeNode(null, 4, null) ,2, null),
                1,
                new TreeNode(new TreeNode(null, 5, null), 3, new TreeNode(null, 6, null))
        );

        // 前序遍历
        preOrder(node);
        System.out.println();

        // 中序遍历
        inOrder(node);

        System.out.println();
        // 后序遍历
        afterOrder(node);
        System.out.println();
    }


    /**
     * 前序遍历
     *      对于每一棵子树，先访问该节点，然后是左子树，最后是右子树
     * @param node 二叉树根节点
     */
    private static void preOrder(TreeNode node){
        // 为空退出
        if (node == null){
            return;
        }
        // 打印当前节点
        System.out.print(node + "\t");
        // 左
        preOrder(node.left);
        // 右
        preOrder(node.right);
    }

    /**
     * 中序遍历
     *      对于每一棵子树，先访问左子树，然后是该节点，最后是右子树
     * @param node 二叉树根节点
     */
    private static void inOrder(TreeNode node){
        // 为空退出
        if (node == null){
            return;
        }
        // 左
        inOrder(node.left);
        // 打印当前节点
        System.out.print(node + "\t");
        // 右
        inOrder(node.right);
    }

    /**
     * 后序遍历
     *      对于每一棵子树，先访问左子树，然后是右子树，最后是该节点
     * @param node 二叉树根节点
     */
    private static void afterOrder(TreeNode node){
        // 为空退出
        if (node == null){
            return;
        }
        // 左
        afterOrder(node.left);
        // 右
        afterOrder(node.right);
        // 打印当前节点
        System.out.print(node + "\t");
    }
}
